- Title
- The g-good-neighbor and g-extra diagnosability of networks
- Creator
- Wang, Shiying; Wang, Mujiangshan
- Relation
- Theoretical Computer Science Vol. 773, p. 107-114
- Publisher Link
- http://dx.doi.org/10.1016/j.tcs.2018.09.002
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2018
- Description
- Diagnosability of a multiprocessor system is an important research topic. The system and interconnection network has a underlying topology, which usually presented by a graph G = (V, E). In 2012, a measurement for fault tolerance of the graph was proposed by Peng et al. This measurement is called the g-good-neighbor diagnosability that restrains every fault-free node to contain at least g fault-free neighbors. In 2016, Zhang et al. proposed a new measurement for fault diagnosis of the graph, namely, the g-extra diagnosabil-ity, which restrains that every fault-free component has at least (g+1) fault-free nodes. A fault set F ⊆ V is called a g-good-neighbor faulty set if the degree d(v) ≥ g for every vertex v in G.−F. A g-good-neighbor cut of G is a g-good-neighbor faulty set F such that G−F is disconnected. The minimum cardinality of g-good-neighbor cuts is said to be the g-good-neighbor connectivity of G. A fault set F ⊆ V is called a g-extra faulty set if every component of G−F has at least (g+1) vertices. A g-extra cut of G is a g-extra faulty set F such that G −F is disconnected. The minimum cardinality of g-extra cuts is said to be the g-extra connectivity of G. The g-good-neighbor (extra) diagnosability and g-good-neighbor (extra) connectivity of many well-known graphs have been widely investigated. In this paper, we show the relationship between the g-good-neighbor (extra) diagnosability and g-good-neighbor (extra) connectivity of graphs.
- Subject
- interconnection network; connectivity; diagnosability; g-good-neighbor
- Identifier
- http://hdl.handle.net/1959.13/1422417
- Identifier
- uon:37827
- Identifier
- ISSN:0304-3975
- Language
- eng
- Reviewed
- Hits: 3987
- Visitors: 1247
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|